package leetcode.code986;

import java.util.ArrayList;
import java.util.List;

public class Solution2 extends Solution986 {

	@Override
	public int[][] intervalIntersection(int[][] A, int[][] B) {
		List<int[]> ans = new ArrayList<>();
		int i = 0, j = 0;

		while (i < A.length && j < B.length) {
			// Let's check if A[i] intersects B[j].
			// lo - the startpoint of the intersection
			// hi - the endpoint of the intersection
			int lo = Math.max(A[i][0], B[j][0]);
			int hi = Math.min(A[i][1], B[j][1]);
			if (lo <= hi)
				ans.add(new int[] { lo, hi });

			// Remove the interval with the smallest endpoint
			if (A[i][1] < B[j][1])
				i++;
			else
				j++;
		}
		return ans.toArray(new int[ans.size()][]);
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
